package leetcode_900;

import helpclass.TreeNode;

/**
 *@author 周杨
 *SmallestSubtreeWithalltheDeepestNodes_865 返回一颗二叉树中具有最大深度的节点的子树  (题目没看太懂)
 *describe:用递归 AC 100%
 *2018年11月6日 上午11:56:20
 */
public class SmallestSubtreeWithalltheDeepestNodes_865 {
	class Result {
		TreeNode node;
		int dist;

		Result(TreeNode n, int d) {
			node = n;
			dist = d;
		}
	}

	public TreeNode subtreeWithAllDeepest(TreeNode root) {
		return dfs(root).node;
	}

	public Result dfs(TreeNode node) {
		if (node == null)
			return new Result(null, 0);
		Result L = dfs(node.left), R = dfs(node.right);
		if (L.dist > R.dist)
			return new Result(L.node, L.dist + 1);
		if (L.dist < R.dist)
			return new Result(R.node, R.dist + 1);
		return new Result(node, L.dist + 1);
	}
}
